The present invention relates to a buffer management method for ensuring a certain minimum buffer for each buffer user in an apparatus employing a shared buffer storage, such as an ATM switching apparatus (ATM, Asynchronous Transfer Mode).
In present wide-bard data networks, buffering is a xe2x80x9cbottleneckxe2x80x9d. Buffering is used for temporary data storage in a situation where the receiving party is unable to receive the data at the same rate as it has been transmitted. The data to be buffered is generally stored in a so-called buffer storage. In prior art, several buffer management methods for maximising the utilisation of the available buffering and transfer capacity are known.
In general, the sharing of a buffer is closely associated with the decision-making process that produces the decision as to what part of the data in the buffer is to be deleted when data of a higher priority level is coming in or whether the data is to be admitted into the buffer at all.
In principle, three types of buffer management method are known: complete partitioning, complete sharing and partial sharing. Complete partitioning means that the entire buffer capacity is allocated to concurrent users or entities (e.g. priority classes or queues) so that the sum of segments allocated does not exceed the buffer capacity. Complete sharing means that all users are allowed to occupy buffer space until the buffer is full. Users may be assigned individual maximum limits to ensure that a single user will not occupy the whole buffer space. When the sum of the maximum limits approaches the total buffer capacity, complete sharing approaches complete partitioning. The implementation of complete sharing often comprises a so-called pushout feature, which means that a higher-priority cell or data received in the buffer supersedes a lower-priority cell or data if the buffer is full. In partial sharing (also known as threshold method), a certain threshold is designated for the defeat of each priority. In this case, data belonging to a given class is admitted into the buffer if the amount of data of this priority class in the buffer is below the threshold designated for that class. The pushout mechanism or threshold method requires that different priorities have been defined for data.
A problem with the threshold method is that it is impossible to guarantee a minimum buffer while at the same time using the buffer effectively. A problem with the pushout method is that the method is difficult to implement using equipment known so far. Moreover, it is difficult to judge and identify the data or cell to be deleted when data of a higher priority level is received in the buffer.
Another problem with prior-art methods is that while the counters used to count the data packets or cells do know the actual number of packets or cells, they do not know what part of the cells is guaranteed and what part is not.
The object of the present invention is to eliminate the problems described above.
A specific object of the present invention is to disclose a new type of buffer management method. A further object of the invention is to disclose a buffer management method in which minimum thresholds and rejection rules are observed so that a minimum buffer space can be guaranteed for each user of the buffer and the remaining buffer space can be allocated dynamically among all users.
The invention relates to a buffer management method for sharing the storage capacity F of the buffer between buffer users, such as queues, communication links or equivalent, which store packets in the buffer. A packet may be an ATM cell, and IP packet (IP, Internee Protocol) of equivalent, depending on the use and the application. In this method, the total number of packets stored in the buffer and the total number stored by each user are counted or determined. Based on these, the amount of buffer capacity to be granted to the users is controlled with respect to each packet, i.e. each time when a user attempts to store a packet in the buffer, a function determining whether the user is to be accorded buffer space or not is executed.
According to the invention, a modified total number of packets T* stored in the buffer is determined from the equation:                                                                                           T                  *                                =                                  xe2x80x83                                ⁢                                                      ∑                                          i                      =                      1                                        N                                    ⁢                                      xe2x80x83                                    ⁢                                      max                    ⁢                                          {                                                                        a                          ⁡                                                      (                            i                            )                                                                          ,                                                  c                          ⁡                                                      (                            i                            )                                                                                              }                                                                                  ,                              xe2x80x83                            ⁢              where                                                                                          N                =                                  xe2x80x83                                ⁢                                  total                  ⁢                                      xe2x80x83                                    ⁢                  number                  ⁢                                      xe2x80x83                                    ⁢                  of                  ⁢                                      xe2x80x83                                    ⁢                  users                                            ;                                                                                                            a                  ⁡                                      (                    i                    )                                                  =                                  xe2x80x83                                ⁢                                  minimum                  ⁢                                      xe2x80x83                                    ⁢                  buffer                  ⁢                                      xe2x80x83                                    ⁢                  capacity                  ⁢                                      xe2x80x83                                    ⁢                                      (                                                                  a                        ⁡                                                  (                          i                          )                                                                    ≥                      0                                        )                                    ⁢                                      xe2x80x83                                    ⁢                  allocated                  ⁢                                      xe2x80x83                                    ⁢                  for                  ⁢                                      xe2x80x83                                    ⁢                  user                  ⁢                                      xe2x80x83                                    ⁢                  i                                            ;                              xe2x80x83                            ⁢              and                                                                                                            c                  ⁡                                      (                    i                    )                                                  =                                  xe2x80x83                                ⁢                                  actual                  ⁢                                      xe2x80x83                                    ⁢                  buffer                  ⁢                                      xe2x80x83                                    ⁢                  capacity                  ⁢                                      xe2x80x83                                    ⁢                  occupied                  ⁢                                      xe2x80x83                                    ⁢                  by                  ⁢                                      xe2x80x83                                    ⁢                  user                  ⁢                                      xe2x80x83                                    ⁢                  i                  ⁢                                      xe2x80x83                                    ⁢                  at                  ⁢                                      xe2x80x83                                    ⁢                  the                                            ⁢                              xe2x80x83                                                                                                        xe2x80x83                            ⁢                              reference                ⁢                                  xe2x80x83                                ⁢                                  instant                  .                                                                                        (        1        )            
As in buffer management in general, buffer control in this invention, too, is based on rejection of packets, i.e. on making a decision as to whether a packet is to be admitted into the buffer or not. Further, according to the invention, if the conditions T*xe2x89xa7F and c(i)xe2x89xa7a(i) are true, then a packet of user i is rejected without storing it in the buffer.
It is to be noted that equation (1) is a logical representation of the counter T*. The counter T* may be implemented by various systems, including, but not limited to, an apparatus employing a shared buffer storage, such as an ATM switching apparatus.
For example, the following methods can be used to determine the value of the counter T*:
1) Each time a packet comes in or leaves the buffer, T* is calculated in, accordance with equation (1).
2) T* is calculated in accordance with equation (1). After this, the following is done: When a packet is coming in to the buffer for user i, the value of the counter T* is increased if the packet is accepted and c(i)xe2x89xa7a(i) (before c(i) is updated). When a packet of user i leaves the buffer, the value of the counter T* is decreased if c(i) greater than a(i) (before c(i) is updated).
As compared with prior art, the invention has the advantage that a minimum buffer can be reliably guaranteed for each buffer user.
Another advantage of the invention is that the buffer capacity left over after the allocation of a minimum capacity for the users can be flexibly and dynamically shared among users that may need it. In this way, the objects of guaranteeing a minimum buffer for each user and effective buffer utilisation are realised.
The buffer management method, calculation of a modified total amount and rejection rule described above can be applied in many ways. In a preferred embodiment of the invention, the buffer management method can be applied among a selected set of users U, in which case the modified total T* is calculated from the equation                                                                                           T                  *                                =                                  xe2x80x83                                ⁢                                                      ∑                                                                  i                        =                        1                                                                    i                        ∈                        U                                                              N                                    ⁢                                      xe2x80x83                                    ⁢                                      max                    ⁢                                          {                                                                        a                          ⁡                                                      (                            i                            )                                                                          ,                                                  c                          ⁡                                                      (                            i                            )                                                                                              }                                                                                  ,                              xe2x80x83                            ⁢              where                                                                                          N                =                                  xe2x80x83                                ⁢                                  total                  ⁢                                      xe2x80x83                                    ⁢                  number                  ⁢                                      xe2x80x83                                    ⁢                  of                  ⁢                                      xe2x80x83                                    ⁢                  users                                            ;                                                                                          U                =                                  xe2x80x83                                ⁢                                  set                  ⁢                                      xe2x80x83                                    ⁢                  of                  ⁢                                      xe2x80x83                                    ⁢                  selected                  ⁢                                      xe2x80x83                                    ⁢                  users                                            ;                                                                                          a                ⁡                                  (                  i                  )                                            =                              xe2x80x83                            ⁢                              minimum                ⁢                                  xe2x80x83                                ⁢                capacity                ⁢                                  xe2x80x83                                ⁢                                  (                                                            a                      ⁡                                              (                        i                        )                                                              ≥                    0                                    )                                ⁢                                  xe2x80x83                                ⁢                allocated                ⁢                                  xe2x80x83                                ⁢                for                ⁢                                  xe2x80x83                                ⁢                user                ⁢                                  xe2x80x83                                ⁢                i                ⁢                                  xe2x80x83                                ⁢                in                                                                                                        xe2x80x83                            ⁢                                                the                  ⁢                                      xe2x80x83                                    ⁢                  buffer                                ;                                  xe2x80x83                                ⁢                and                                                                                                        c                ⁡                                  (                  i                  )                                            =                              xe2x80x83                            ⁢                              actual                ⁢                                  xe2x80x83                                ⁢                buffer                ⁢                                  xe2x80x83                                ⁢                capacity                ⁢                                  xe2x80x83                                ⁢                occupied                ⁢                                  xe2x80x83                                ⁢                by                ⁢                                  xe2x80x83                                ⁢                user                ⁢                                  xe2x80x83                                ⁢                i                ⁢                                  xe2x80x83                                ⁢                at                ⁢                                  xe2x80x83                                ⁢                the                                                                                                        xe2x80x83                            ⁢                              reference                ⁢                                  xe2x80x83                                ⁢                                  instant                  .                                                                                        (        2        )            
In this embodiment, a certain portion FQ(U)xe2x89xa6F of the storage capacity of the buffer is allocated for the selected users, and the storage of additional packets by user i is inhibited if the total T*xe2x89xa7FQ(U) and c(i)xe2x89xa7a(i). Users not included in set U may use any method to share the remaining portion Fxe2x88x92FQ(U) of the buffer.
Further, it is possible to form user groups k=1,2, . . . ,M. The members of a group have an equal minimum buffer capacity each. If M=1, then all users have equal minimum buffers.
If the method is used in ATM, then UBR communication can be included by setting the minimum buffer as a(i)=0. For VBR communication, the minimum buffer can be set to be equal to the maximum burst size of the connection: a(i)=MBS(i). In this case, a VBR connection has its own buffer area of a size equal to the maximum burst size, and this area cannot be occupied by others. (If additionally bursts exceeding MBS(i) are eliminated by policing, then the VBR connection itself will not take up any space in the shared buffer area!). CBR (CBR, Constant Bit Rate) communication can be handled in a corresponding manner.
In a preferred embodiment of the buffer management method of the invention, in addition to the above, a maximal buffer capacity b(i) that the user may occupy in the buffer at a time is defined for each user. In this embodiment, the storage of additional packets by the user is also inhibited when the maximal user-specific buffer capacity has been reached, i.e. the condition c(i)xe2x89xa7b(i) is valid. The maximal buffer capacity b(i) can also be changed dynamically e.g. on the basis of the free capacity available in the buffer. This makes it possible to guarantee a certain fairness between the users in the sharing of buffer capacity exceeding the modified total T*.